1. Technical Field
The present invention relates to the distribution and management of session keys in a communications network, for example, an internet broadcast application.
2. Related Art
Recent interest in group communications with a very large set of receivers has led to a need for secure communications systems that scale efficiently as the number of users increases. For example, developers of Internet broadcast applications such as teleconferencing and video-on-demand desire more effective secure communication between very large numbers of users.
In group communications, special problems arise in a dynamic group in which new members can join the group and current members can leave the group, either voluntarily or by being ejected. There are at least three security issues that to be considered:
1. Group key security (a group key being a key which allows access to information by all the members of the group). It should be computationally infeasible for a person outside the group to discover the group key.
2. Forward Security. A system has forward security if a member leaving the group cannot get access to later group keys and so cannot decrypt data sent after that user has left the group.
3. Backward Security. A system has backward security if a member joining the group cannot get access to earlier group keys and so cannot decrypt data sent before that user joined the group.
A simple multi-user system provides a key distribution centre (or key server) that is in direct contact with every member of the group. Each member shares a key with the key distribution centre (the member's individual key) and, for group communications, all members share a group key. Each time a member joins or leaves the group, the group key must be updated to ensure backward or forward security as the case may be. When a new member joins the group, the new group key is sent to the new member, encrypted using the new member's individual key and is sent, as a broadcast, to all existing members, encrypted using the previous group key. Thus a join event is relatively straightforward and scales well in terms of computational effort, broadcast bandwidth requirements and secure unicast requirements as the number of users increases.
When a member leaves the group, the new group key must be individually sent to members using that member's individual key since, if the new group key was encrypted using the previous group key, the user that has just left the group would be able to generate that new group key (it being assumed that that user would receive the encrypted new key by permitted means or otherwise).
It can be seen that, the computational and communication requirements scale in a linear manner with the number of users. Thus, in a system with a very large number of users, the computational and communication requirements when a member leaves the group can become prohibitive.
It can be seen that there is a need to provide a key management system that scales effectively as the number of users increases. In particular, there is a need for a key management system in which the computational time of the server and the users, the memory storage requirements of the users and the broadcast bandwidth requirements all scale effectively as the number of users increases.
A hierarchical key tree is disclosed in “Key Management for Multicast: Issues and Architectures” by D Wallner et. al. (National Security Agency, June 1999, www.ietf.org/rfc/rfc2627.txt).
A hierarchical binary tree is an efficient tree-based key management technique. A hierarchical binary tree works as follows. A multicast group has N members (M1 to MN). A new member joins the group by contacting the controller via a secure unicast channel. At the time the new member joins, the new member and the controller negotiate a pairwise secret key.
The controller stores a binary tree structure in which each node contains a key. At the leaves of the tree there are the N secret keys that the controller has negotiated with each of the members of the group. Each member stores a subset of the controller's keys. The subset of keys stored by a member is the set of keys in the path from the leaf to the root of the tree including the leaf and the root itself. The root node represents the key used to encrypt data during the group communication; all other keys in the tree are auxiliary keys used only to facilitate efficient key updates.
FIG. 1 shows a hierarchical tree for a system having three users, M1, M2 and M3. The tree has a root node K14 connected to two nodes K12 and K34. K12 in turn is connected to nodes K1 and K2. Node K34 is connected to node K3. The users M1, M2 and M3 are associated with nodes K1, K2 and K3 respectively. Each of the nodes K1, K2, K3, K12, K34 and K14 represents a cryptographic key.
In a hierarchical tree structure, each member of the group knows all the keys from its leaf node up to the root node. Thus, user M1 knows the keys for nodes K1, K12 and K14. User M2 knows the keys for nodes K2, K12 and K14. User M3 knows the keys for nodes K3, K34 and K14.
Thus, every user knows the key at the root node K14. Accordingly, the root key can be used to encrypt all transmissions involving users M1, M2 and M3.
If a new user M4 joins the group, that user must be added to the hierarchical tree. FIG. 2 shows the same hierarchical tree as FIG. 1, except that nodes K14 and K34 have been replaced with nodes K14′ and K34′ and the new user M4 is attached via new node K4 to node K34′. The keys K14′ and K34′ are different from the previous keys K14 and K34 to ensure that the system has backward security. This is implemented by the key server at the root node. Key 4 is generated by the key server and keys K34 and K14 are updated (to K34′ and K14′ respectively) by the key server.
The new user M4 needs to know the keys K4, K34′ and K14′. This information is transmitted to M4 via a secure channel.
The key server informs the other members of the group of the new keys by sending encrypted broadcasts that all members can receive (non-members will be able to receive the broadcast but they will not be able to decrypt the information sent). The following broadcasts are made: K34′ encrypted with K3, K14′ encrypted with K34′ and K14′ encrypted with K12.
User M3 knows the key K3 and can therefore decrypt K34′ encrypted with K3 to arrive at K34′. From this, user M3 can decrypt K14′ encrypted with K34′. Similarly, users M1 and M2 both know key K12 and can therefore decrypt K14′ encrypted with K12. Thus all users once again know all of the keys from their leaf of the tree to the root. Transmissions involving the members of the group (now including the new member M4) can be encrypted with the new root key K14′.
If user M3 leaves the group, that user must be removed from the hierarchical tree. FIG. 3 shows the hierarchical tree of FIG. 2, except that user M3 and node K3 have been removed from the tree, and nodes K14′ and K34′ have been updated to K14″ and K34″ respectively. Thus all of the keys that were known to M3 (K3, K34′ and K14′) have been either removed or updated. Thus the system has forward security.
The key server updates keys K14′ and K34′ to generate keys K14″ and K34″ respectively. The key server then broadcasts K34″ encrypted with K4 and K14″ encrypted with K34″. The user M4 knows key K4 and so can decrypt K34″ encrypted with K4 to arrive at K34″. Similarly, M4 can decrypt K14″ encrypted with K34″ to arrive at the new root key K14″. As before, K14″ must also be broadcast encrypted with K12 so that users M1 and M2 can obtain the new root key. Since previous user M3 did not know either key K4 or key K12, he cannot obtain key K14″ from the broadcast messages.
The principal advantage associated with the use of a tree for the organisation of users in a multi-user system is that any individual user only knows a subset of the keys of the system. Thus, when a user leaves the group, only that subset needs to updated to ensure backward security. When a user leaves the group, the number of keys that have to be updated is of the order of log(N), where N is the number of users. Thus, the number of transmissions required to re-key the tree scales as the number of users increases.
It is not essential that a hierarchical tree is a binary tree. A P-ary tree can be used. As the value P rises, the storage requirement for each user decreases, but at the expense of an increase in the number of transmissions required from the key server.
A variant of the hierarchical tree described above is the one-way function tree described in “Key Management for Large Dynamic Groups: One-Way Function Trees and Amortized Initialization” by D Baleson et. al. (TIS Labs at Network Associates, 26 Feb. 1999).
The one-way function tree described by Baleson et. al. is a binary tree. Each node of the tree is associated with two keys: an unblinded key K(x) and a blinded key K′(x). The session key that is used to encrypt application data (such as a video broadcast) includes both the blinded and unblinded keys of the root node. The blinded key K′(x) is derived from the unblinded key K(x) using a one-way function (see below). K′(x) is ‘blinded’ in the sense that it is computationally infeasible to find K(x) from K′(x).
Each node in the hierarchical tree (except the leaf nodes) has two children: x_left and x_right. The parent node K(x) is defined by the following formula:K(x)=K′(x_left) XOR K′(x_right)
The members of the system are associated with the leaves of the tree. Each member knows the blinded keys for every node that is a sibling of any of the nodes on the branch of the tree extending from the user to the root of the tree.
Taking the binary tree of FIG. 1 as an example, the user M1 would know the blinded and unblinded keys for node K1 (K1 and K′1) and would know the blinded keys for nodes K2 (the sibling of K1) and K34 (the sibling of K12) (the keys K′2 and K′34 respectively). From this information, the user M1 can generate the unblinded key for K12 from the blinded keys K′1 and K′2 thus:K12=K′12 XOR K′2
Using a one-way function generates the blinded key K′12 of node K12 (K′12) with the result that the twin keys (blinded and unblinded) of K12 (K12 and K′12 respectively) are generated. Further, user M1 can generate the unblinded key of node K14 from the blinded keys K′12 and K′34 thus:K14=K′12 XOR K′34
Using a one-way function generates the blinded key of K14 (K′14) so that the twin keys of the root node K14 (K14 and K14′) are known.
The purpose of the blinded and unblinded keys is the reduction of the number of keys that a key distribution server has to send during key update operations. The key distribution server must send log2(N) updates in the form blinded keys (where N is the number of users). The updates are encrypted to ensure that only the members who should receive the updates have the necessary keys to decrypt the messages and receive the updates.
One-way functions such as that used in the one-way function tree described above are mathematical functions that are relatively easy to compute in a first direction but is computationally infeasible to compute in the other (reverse) direction.
Message digest, fingerprint or compression functions are examples of a first class of one-way functions (functions of this class are commonly called “hash functions”). A message digest function is a mathematical function that takes a variable length input string and converts it into a fixed-length binary sequence. Modern message digest functions typically produce hash values of 128 bits or longer.
Message digest functions are used to create a digital signature for a document. Since it is computationally infeasible to deliberately produce a document that will hash to a particular hash value and extremely unlikely to find two documents that hash to the same value, a document's hash value can serve as a cryptographic equivalent of the document.
Examples of message digest functions are MD4 (Message Digest 4), MD5 (Message Digest 5, see “The MD5 Message-Digest Algorithm” by R. Rivest, MIT Laboratory for Computer Science and RSA Data Security, Inc., April 1992, www.ietf.org/rfc/rfc1321.txt) and SHA (Secure Hash Algorithm). SHA is generally considered to be the most secure of the three.
One-way functions can also be generated using pseudo random function (PRF) with varying input and output lengths. A suitable known PRF is an encryption algorithm called RC5. The RC5 encryption algorithm is a fast symmetric cipher algorithm suitable for hardware or software implementation and has low memory and computational requirements.
Another example of a one-way function is a trapdoor one-way function. The inverse of a trapdoor one-way function is easily generated if the trapdoor is known but difficult otherwise.
A public-key cryptosystem can be designed using a trapdoor one-way function. Public-key cryptosystems are well known in the art (see Digital Communications Fundamentals and Applications, Bernard Sklar, Prentice-Hall International, Inc., 1998 edition, pages 698 to 702). The public key in such a system gives information about the particular instance of the function; a private key gives information about the trapdoor. The function can be computed in the forward direction only unless the trapdoor is known. The forward direction is used for encryption and signature verification. The reverse direction is used for decryption and signature generation.
The prior art has addressed some of the problems associated with the distribution and management of session keys in a communications network. In particular, the use of hierarchical trees provides systems in which bandwidth usage and key storage by the key distribution server scales logarithmically as the number of users increases.
There are problems with the prior art systems. For example, the algorithms described all require the update information to be encrypted in such a manner that only members entitled to the update information have the necessary keys to decrypt that information.